/*
 * @lc app=leetcode.cn id=1539 lang=javascript
 *
 * [1539] 第 k 个缺失的正整数
 */

// @lc code=start
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findKthPositive = function (arr, k) {
  if (arr[0] > k) {
    return k;
  }
  let l = 0,
    r = arr.length;
  while (l < r) {
    const mid = Math.floor((l + r) / 2);

    //   arr[mid] - mid - 1代表 0 到 mid缺失的数量（如果不缺失arr[mid]其实就等于mid+1）
    //   如果mid缺失数量大于k 则包含了k，右区间左移
    //   如果mid缺失数量大于小于 则不包含k，左区间右移
    //   当结束时 k就等于left
    if (arr[mid] - mid - 1 >= k) {
      r = mid;
    } else l = mid + 1;
  }
  //   return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1];
  return k + l;
};
// @lc code=end
